package leetcode.problems;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by gmwang on 2020/2/1
 * Convert Sorted List to Binary Search Tree
 * 排序列表转换为二叉搜索树
 */
public class ConvertSortedListToBinarySearchTree {
    /**
     * Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
     *
     * For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
     *
     * Example:
     *
     * Given the sorted linked list: [-10,-3,0,5,9],
     *
     * One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     **/
    public TreeNode sortedListToBST(ListNode head) {
        List list = getList(head);
        if(list.size() == 0){
            return null;
        }
        TreeNode treeNode = getTreeNode(list, 0, list.size() -1);
        return treeNode;
    }
    public List getList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        return list;
    }
    public TreeNode getTreeNode(List<Integer> list,int low,int high) {
        int mid = (low + high) / 2;
        if(low > high){
            return null;
        }
        TreeNode treeNode = new TreeNode(list.get(mid));
        treeNode.left = getTreeNode(list,low,mid - 1);
        treeNode.right = getTreeNode(list,mid + 1,high);
        return treeNode;
    }

    @Test
    public void test(){
        ListNode root = new ListNode(-10);
        ListNode root1 = new ListNode(-3);
        root.next = root1;
        ListNode root2 = new ListNode(0);
        root1.next = root2;
        ListNode root3 = new ListNode(5);
        root2.next = root3;
        ListNode root4 = new ListNode(9);
        root3.next = root4;
        TreeNode treeNode = sortedListToBST(root);
        System.out.println(treeNode);
    }
}
